package xyz.scootaloo.oj.offer

import org.junit.Test
import java.lang.StringBuilder

/**
 * @author flutterdash@qq.com
 * @since 2021/4/13 9:39
 */
class P38 {

    private fun permutation(s: String): Array<String> {
        val res = HashSet<String>()
        val path = BooleanArray(s.length)
        dfs(s, res, StringBuilder(), path)
        return res.toArray(arrayOf())
    }

    private fun dfs(
        s: String, res: HashSet<String>, cache: StringBuilder, path: BooleanArray
    ) {
        if (cache.length == s.length) {
            res.add(cache.toString())
            return
        }

        for (idx in s.indices) {
            if (path[idx])
                continue
            cache.append(s[idx])
            path[idx] = true

            dfs(s, res, cache, path)

            path[idx] = false
            cache.setLength(cache.length - 1)
        }
    }

    @Test
    fun test0() {
        val input = "abc"
        println(permutation(input).contentToString())
        val input2 = "aab"
        println(permutation(input2).contentToString())
    }

}
